package Top_Interview_Questions.Stack;

import java.util.*;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/7 15:12
 * <p>
 * 功能描述:
 */
public class _0155 {

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(2);
        minStack.push(0);
        minStack.push(-9);
        minStack.push(4);
        minStack.push(2);

        System.out.println(minStack.getMin());
        minStack.pop();
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());

    }
}
/**
 * 别人的题解: 2020/1/7 16:06
 *
 * 解析:
 * 1.https://leetcode-cn.com/problems/min-stack/solution/
 *   shi-yong-fu-zhu-zhan-tong-bu-he-bu-tong-bu-python-/
 * 2.自己debug一下这个辅助栈做法,就明白了了
 * 3.因为返回值为int,这里if后面不抛异常,编译会出错。
 * 4.data和helper这两个栈push之后的深度始终一样,用!data.isEmpty()或者!helper.isEmpty()
 * 都是一样的
 */
class MinStack {

    // 数据栈
    private Stack<Integer> data;
    // 辅助栈
    private Stack<Integer> helper;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        data = new Stack<>();
        helper = new Stack<>();
    }

    // 思路 1：数据栈和辅助栈在任何时候都同步

    public void push(int x) {
        // 数据栈和辅助栈一定会增加元素
        data.add(x);
        if (helper.isEmpty() || helper.peek() >= x) {
            helper.add(x);
        } else {
            helper.add(helper.peek());
        }
    }

    public void pop() {
        // 两个栈都得 pop
        if (!data.isEmpty()) {
            helper.pop();
            data.pop();
        }
    }

    public int top() {
        if(!data.isEmpty()){//4.
            return data.peek();
        }
        throw new RuntimeException("栈中元素为空，此操作非法");//3.
    }

    public int getMin() {
        if(!helper.isEmpty()){
            return helper.peek();
        }
        throw new RuntimeException("栈中元素为空，此操作非法");
    }
}






///**
// * 第一遍解题  2020/1/7 15:12
// *
// * 执行结果:
// * 执行用时 :51 ms, 在所有 Java 提交中击败了41.93%的用户
// * 内存消耗 :48 MB, 在所有 Java 提交中击败了21.12%的用户
// */
//class MinStack {
//
//    Stack<Integer> stack = new Stack<>();
//    List<Integer> list = new ArrayList<>();
//
//    /**
//     * initialize your data structure here.
//     */
//    public MinStack() {
//    }
//
//    public void push(int x) {
//        list.add(x);
//        Collections.sort(list);
//        stack.push(x);
//
//    }
//
//    public void pop() {
//        Integer x = stack.pop();
//        list.remove(list.indexOf(x));
//    }
//
//    public int top() {
//        return stack.peek();
//    }
//
//    public int getMin() {
//        return list.get(0);
//    }
//}
